Basic structures
Generating functions
Proof techniques
Combinatorial identities
Polytopes
In enumerative combinatorics, a “bijective proof” refers to a basic method of counting the number of structures of a certain type supported on a finite set of underlying points, by analyzing structure in two different ways. It is really a special case of “categorification”: an identity where and are natural number expressions is proved by taking underlying cardinalities of a bijection between sets of structures, hence the name. (If taking cardinalities is an example of “decategorifying”, then going the other way from to would be “categorifying” or promoting an equation to an isomorphism.)
In some sense this is what the theory of species is all about: formalizing the operations adhering to bijective proofs. Often bijective proofs give an impression of elegance or enlightenment: rather than prove natural number or polynomial identities through acts of symbolic manipulation, one sees the identity by drawing pictures of structures that the two sides of the identity are counting.
For the moment we’ll just jot down some possible examples for illustrating the method; these are to be filled in later, or to be linked to other nLab articles where the bijective proof is given.
See for now binomial theorem.
For more details, see the Wikipedia article.
Algebraically, one may introduce the -binomial coefficients by introducing a -affine plane (or quantum affine plane, to be connected with quantum affine algebra) and its associated (non-commutative) algebra
where is a parameter, and then writing .
However, an illuminating combinatorial interpretation of the -binomial coefficients is that they count points in a Grassmannian consisting of -dimensional linear subspaces of an -dimensional vector space over a finite field of cardinality . This interpretation can be used to provide a bijective proof of the -Pascal identity
For, if we choose a standard affine hyperplane in , then any linear -plane in either intersects in an affine -plane in the affine -space, or intersects in the empty set, i.e., is contained in the linear space . The number of satisfying the latter condition is , and the number of satisfying the former is in bijection with the number of -dimensional affine subspaces of , which is times the number of linear subspaces divided by , the number of translations which stabilize a given affine subspace. (Maybe to be rewritten later.)
Cayley’s theorem, here not to be confused with Cayley’s observation that every group (monoid) is a subgroup (submonoid) of a permutation group (endofunction monoid), says that the number of tree structures on an -element set is .
There are many proofs of this fact in the literature. One, due to Gilbert Labelle and made popular by André Joyal, proceeds by establishing a bijection between trees equipped with a pair of nodes (allowing ) and the number of endofunctions on .
On the one hand, such a structure on can be identified with a linearly ordered set (the path from to in ) together with, for each node along that path, a rooted tree structure consisting of nodes for which the shortest path in from to ends at . (As a subgraph of , this naturally forms a tree rooted at .) Thus, such a structure on determines and is determined by an equivalence relation on , a rooted tree structure on each equivalence class, and a linear ordering of the set of equivalence classes.
On the other hand, each endofunction on , say , has an eventual image or stable set , on which acts by a permutation (i.e., bijectively). For each , there is a rooted tree which consists of all for which the set of iterates first lands in at . Thus an endofunction on determines and is determined by an equivalence relation on , a rooted tree structure on each equivalence class, and a permutation on the set of equivalence classes.
Since the number of permutations on is equinumerous with the number of linear orderings of , we conclude that the set of “bipointed tree” structures on is equinumerous with the set of endofunctions on . Thus the number of bipointed tree structures on is , and therefore the number of tree structures on is .
One method for proving polynomial identities (equations between polynomials in several variables) is first to give a bijective proof for the special case in which natural numbers are substituted for the variables , and then reason that there are enough natural numbers that the polynomial identity must hold generally.
More formally, two polynomials are equal, , if for all choices of natural numbers . Relatedly, the set is Zariski-dense (i.e., the closure of in equipped with the Zariski topology is all of ).
This is intuitively obvious of course. As a public service, we prove a more general result.
Suppose is an infinite subset of an integral domain . Then a polynomial is uniquely determined by its values it takes at arguments .
It suffices to show that if for every choice of , then . We prove this by induction on . The case is trivial.
Assuming the assertion as induction hypothesis for case , suppose satisfies for all choices and . Then by induction, for each fixed the polynomial is identically zero. Thus if is the field of fractions of , and if we regard as an element of the Euclidean domain under the obvious embedding
then has infinitely many roots in and thus in , forcing to be identically zero.
Last revised on August 26, 2018 at 12:15:59. See the history of this page for a list of all contributions to it.